import collections
import heapq
import sortedcontainers


class FileSharing(object):

    def __init__(self, m):
        """
        :type m: int
        """
        self.index = 1
        self.st = []
        self.d_f = collections.defaultdict(lambda: sortedcontainers.SortedList())
        self.d_u = collections.defaultdict(set)

    def join(self, ownedChunks):
        """
        :type ownedChunks: List[int]
        :rtype: int
        """
        o = set(ownedChunks)
        if not self.st:
            self.d_u[self.index] = o
            index = self.index
            self.index += 1
        else:
            index = heapq.heappop(self.st)
            self.d_u[index] = o
        for f in o:
            self.d_f[f].add(index)
        return index

    def leave(self, userID):
        """
        :type userID: int
        :rtype: None
        """
        node = self.d_u.pop(userID)
        heapq.heappush(self.st, userID)
        for f in node:
            self.d_f[f].remove(userID)

    def request(self, userID, chunkID):
        """
        :type userID: int
        :type chunkID: int
        :rtype: List[int]
        """
        r = list(self.d_f[chunkID])
        if r:
            self.d_u[userID].add(chunkID)
            if userID not in self.d_f[chunkID]:
                self.d_f[chunkID].add(userID)
        return r

